//==--- tools/clang-check/ClangInterpreter.cpp - Clang Interpreter tool
//--------------===//
//===----------------------------------------------------------------------===//
#include <cxxabi.h>
#include <execinfo.h>
#include <stdio.h>
#include <string.h>

#include <iostream>

#include "clang/AST/ASTConsumer.h"
#include "clang/AST/Decl.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/Frontend/CompilerInstance.h"
#include "clang/Frontend/FrontendAction.h"
#include "clang/Tooling/Tooling.h"

// helper functions begin
#define UNRECOVERABLE_ERROR 5
#define safe_assert(cond) \
  _safe_assert(cond, __PRETTY_FUNCTION__, __FILE__, __LINE__)

void frame_backtrace() {
  void *trace[10];
  int size = backtrace(trace, 10);
  char **strings = backtrace_symbols(trace, size);
  printf("Function call trace:\n");
  for (int i = 0; i < size; i++) {
    size_t strlength = strlen(strings[i]);
    char *output_buffer = (char *)malloc(strlength);
    int status = 1;
    abi::__cxa_demangle(strings[i], output_buffer, &strlength, &status);
    if (status == 0) {
      printf("%s\n", output_buffer);
    } else {
      printf("%s\n", strings[i]);
    }
  }
  free(strings);
}

inline void _safe_assert(bool cond, const char *func, const char *file,
                         int line) {
  if (!cond) {
    std::cout << "Counit: safe assert fail." << std::endl;
    std::cout << "\tfunction: " << func << "\tfile: " << file
              << "\tline: " << line << std::endl;
    frame_backtrace();
    fflush(stdout);
    _Exit(UNRECOVERABLE_ERROR);
  }
}

using namespace clang;

class StackFrame {
  /// StackFrame maps Variable Declaration to Value
  /// Which are either integer or addresses (also represented using an Integer
  /// value)
  std::map<Decl *, int64_t> mVars;
  std::map<Stmt *, int64_t> mExprs;
  /// The current stmt
  Stmt *mPC;

  /// 栈帧返回值
  int64_t returnval;

 public:
  StackFrame() : mVars(), mExprs(), mPC() {}

  void bindDecl(Decl *decl, int64_t val) { mVars[decl] = val; }
  int64_t getDeclVal(Decl *decl) {
    safe_assert(mVars.find(decl) != mVars.end());
    return mVars.find(decl)->second;
  }
  void bindStmt(Stmt *stmt, int64_t val) { mExprs[stmt] = val; }
  int64_t getStmtVal(Stmt *stmt) {
    safe_assert(mExprs.find(stmt) != mExprs.end());
    return mExprs[stmt];
  }
  void setPC(Stmt *stmt) { mPC = stmt; }
  Stmt *getPC() { return mPC; }
  int64_t getReturnval() { return returnval; }
  void setReturnval(int64_t val) { this->returnval = val; }
};

class Environment {
  std::vector<StackFrame> mStack;

  FunctionDecl *mFree;  /// Declartions to the built-in functions
  FunctionDecl *mMalloc;
  FunctionDecl *mInput;
  FunctionDecl *mOutput;

  FunctionDecl *mEntry;

  // 全局变量及函数声明
  std::map<Decl *, int64_t> golbalVars;

 public:
  /// Get the declartions to the built-in functions
  Environment()
      : mStack(),
        mFree(NULL),
        mMalloc(NULL),
        mInput(NULL),
        mOutput(NULL),
        mEntry(NULL) {}

  /// Initialize the Environment
  void init(TranslationUnitDecl *unit) {
    for (TranslationUnitDecl::decl_iterator i = unit->decls_begin(),
                                            e = unit->decls_end();
         i != e; ++i) {
      if (FunctionDecl *fdecl = dyn_cast<FunctionDecl>(*i)) {
        if (fdecl->getName().equals("FREE"))
          mFree = fdecl;
        else if (fdecl->getName().equals("MALLOC"))
          mMalloc = fdecl;
        else if (fdecl->getName().equals("GET"))
          mInput = fdecl;
        else if (fdecl->getName().equals("PRINT"))
          mOutput = fdecl;
        else if (fdecl->getName().equals("main"))
          mEntry = fdecl;
      } else if (VarDecl *vdecl = dyn_cast<VarDecl>(*i)) {
        if (vdecl->hasInit()) {
          Stmt *initstmt = vdecl->getInit();
          // TODO 数组是指针类型
          // 本次测试用例中没有数组类型
          if (auto intLiteral = dyn_cast<IntegerLiteral>(initstmt)) {
            // 整数
            llvm::APInt result = intLiteral->getValue();
            int64_t val = result.getSExtValue();
            this->golbalVars[vdecl] = val;
          } else if (auto charLiteral = dyn_cast<CharacterLiteral>(initstmt)) {
            int64_t val = charLiteral->getValue();
            this->golbalVars[vdecl] = val;
          } else {
            // test case 里面只有整数类型，其他暂时不考虑
            std::cerr << "unsupported global varialbe type!" << std::endl;
            safe_assert(true);
          }
        } else {
          // 全局变量未初始化 为0
          this->golbalVars[vdecl] = 0;
        }
      }
    }
    mStack.push_back(StackFrame());
  }

  FunctionDecl *getEntry() { return mEntry; }

  /// !TODO Support comparison operation
  void binop(BinaryOperator *bop) {
    Expr *left = bop->getLHS();
    Expr *right = bop->getRHS();
    int64_t result = 0;  // 保存当前二元表达式的计算结果

    if (bop->isAssignmentOp()) {  // 赋值运算符
      int64_t rightval = this->mStack.back().getStmtVal(right);
      result = rightval;
      auto uop = dyn_cast<UnaryOperator>(left);
      if (DeclRefExpr *declexpr = dyn_cast<DeclRefExpr>(left)) {
        Decl *decl = declexpr->getFoundDecl();
        this->setDeclVal(decl, rightval);
      } else if (ArraySubscriptExpr *array =
                     dyn_cast<ArraySubscriptExpr>(left)) {
        int64_t *elementptr =
            reinterpret_cast<int64_t *>(this->mStack.back().getStmtVal(array));
        *elementptr = rightval;
      } else if (uop &&
                 uop->getOpcode() == clang::UnaryOperatorKind::UO_Deref) {
        int64_t *ptr =
            reinterpret_cast<int64_t *>(this->mStack.back().getStmtVal(uop));
        *ptr = rightval;
      }

    } else {
      int64_t rightValue = mStack.back().getStmtVal(right);
      int64_t leftValue = mStack.back().getStmtVal(left);
      auto opc = bop->getOpcode();

      // *(a + 2)
      if (left->getType()->isPointerType() &&
          right->getType()->isIntegerType()) {
        assert(opc == BO_Add || opc == BO_Sub);
        rightValue *= sizeof(int64_t);
      } else if (left->getType()->isIntegerType() &&
                 right->getType()->isPointerType()) {
        assert(opc == BO_Add || opc == BO_Sub);
        leftValue *= sizeof(int64_t);
      }

      switch (opc) {
        default:
          llvm::errs() << "Unhandled binary operator.";
        case BO_Add:
          result = leftValue + rightValue;
          break;
        case BO_Sub:
          result = leftValue - rightValue;
          break;
        case BO_Mul:
          result = leftValue * rightValue;
          break;
        case BO_Div:
          result = leftValue / rightValue;
          break;
        case BO_EQ:
          result = leftValue == rightValue;
          break;
        case BO_NE:
          result = leftValue != rightValue;
          break;
        case BO_LT:
          result = leftValue < rightValue;
          break;
        case BO_GT:
          result = leftValue > rightValue;
          break;
        case BO_LE:
          result = leftValue <= rightValue;
          break;
        case BO_GE:
          result = leftValue >= rightValue;
          break;
      }
    }
    // 保存此二元表达式的值到栈帧
    mStack.back().bindStmt(bop, result);
  }

  void unaryop(UnaryOperator *uop) {
    typedef UnaryOperatorKind Opcode;
    int64_t result = 0;

    // 算数运算：+, -, ~, !
    // 自增自减：++, --（分前缀和后缀）
    // 地址操作： * []
    // 本次实验要求不涉及 & 取地址运算符

    Opcode opc = uop->getOpcode();
    int64_t value = mStack.back().getStmtVal(uop->getSubExpr());

    switch (opc) {
      default:
        llvm::errs() << "Unhandled unary operator.";
      case UO_Plus:
        result = value;
        break;
      case UO_Minus:
        result = -value;
        break;
      case UO_Not:
        result = ~value;
        break;
      case UO_LNot:
        result = !value;
        break;
      case UO_Deref:
        // TODO 指针解引用
        // 产生的是一个左值，oup指令绑定一个待解引用的指针
        // 后续根据是赋值操作还是取值操作对 (*ptr)进行解引用
        result = value;
        break;
    }

    // 保存此一元表达式的值到栈帧
    this->mStack.back().bindStmt(uop, result);
  }

  void decl(DeclStmt *declstmt) {
    // 一个declstmt中可以有多个decl
    /* eg.
    -DeclStmt 0x55d380020918 <line:8:3, col:15>
    | |-VarDecl 0x55d3800207f8 <col:3, col:11> col:7 used a 'int' cinit
    | | `-IntegerLiteral 0x55d380020860 <col:11> 'int' 1
    | `-VarDecl 0x55d380020898 <col:3, col:14> col:14 used b 'int'
    */
    for (DeclStmt::decl_iterator it = declstmt->decl_begin(),
                                 ie = declstmt->decl_end();
         it != ie; ++it) {
      Decl *decl = *it;
      if (VarDecl *vardecl = dyn_cast<VarDecl>(decl)) {
        QualType type = vardecl->getType();

        if (type->isIntegerType() || type->isPointerType()) {
          // int a; int a = 1; int *a; int *a = MALLOC(10); 四种情况
          if (vardecl->hasInit()) {
            mStack.back().bindDecl(
                vardecl, mStack.back().getStmtVal(vardecl->getInit()));
          } else {
            mStack.back().bindDecl(vardecl, 0);  // 新定义的变量初始化为 0
          }
        } else if (type->isArrayType()) {
          // 暂时不考虑带初始化的数组声明的情况
          const ConstantArrayType *array =
              dyn_cast<ConstantArrayType>(type.getTypePtr());
          int64_t size = array->getSize().getSExtValue();
          int64_t *arrayStorage = new int64_t[size];
          // 测试用例中没有对数组初始化的情况，这里简单的初始化为0
          // 有初始化处理也不复杂，只是比较繁琐，需要考虑两种情况
          // array[3] = {0,1,2}
          // array[3] = {0}
          for (int64_t i = 0; i < size; i++) {
            arrayStorage[i] = 0;
          }
          // 栈帧保存数组首地址
          int64_t ptr = reinterpret_cast<int64_t>(arrayStorage);
          mStack.back().bindDecl(vardecl, ptr);
        }
        // mStack.back().bindDecl(vardecl, 0);
      }
    }
  }

  void declref(DeclRefExpr *declref) {
    mStack.back().setPC(declref);
    QualType type = declref->getType();
    if (type->isIntegerType() || type->isArrayType() || type->isPointerType()) {
      Decl *decl = declref->getFoundDecl();
      DeclContext *parentcontext = decl->getDeclContext();
      int64_t val;
      // 判断引用的变量区域，是全局还是局部
      if (parentcontext->isTranslationUnit()) {
        val = this->golbalVars[decl];
      } else if (parentcontext->isFunctionOrMethod()) {
        val = mStack.back().getDeclVal(decl);
      } else {
        std::cout << "unsupported decl scope " << std::endl;
        assert(1);
      }

      mStack.back().bindStmt(declref, val);
    }
  }

  void cast(CastExpr *castexpr) {
    // TODO setpc作用是什么？
    QualType type = castexpr->getType();
    const char *castname = castexpr->getCastKindName();
    // printf("cast type name is: %s \n", castname);
    // 数组会被cast指令转化为指针类型
    if (type->isIntegerType() ||
        type->isPointerType() && !type->isFunctionPointerType()) {
      Expr *expr = castexpr->getSubExpr();
      // subexpr如果为数组声明引用（DeclRefExpr）时，expr 中存放的是数组首地址
      auto array = dyn_cast<ArraySubscriptExpr>(expr);
      auto deref = dyn_cast<UnaryOperator>(expr);
      if (array != nullptr &&
          castexpr->getCastKind() == clang::CK_LValueToRValue) {
        // 一定是左值到右值的转换吗
        int64_t *eleptr =
            reinterpret_cast<int64_t *>(mStack.back().getStmtVal(expr));
        int64_t val = *eleptr;
        this->mStack.back().bindStmt(castexpr, val);
      } else if (deref &&
                 deref->getOpcode() == clang::UnaryOperatorKind::UO_Deref &&
                 castexpr->getCastKind() ==
                     clang::CastKind::CK_LValueToRValue) {
        int64_t *ptr =
            reinterpret_cast<int64_t *>(this->mStack.back().getStmtVal(deref));
        int64_t val = *ptr;
        this->mStack.back().bindStmt(castexpr, val);
      } else {
        int64_t val = mStack.back().getStmtVal(expr);
        this->mStack.back().bindStmt(castexpr, val);
      }
    }
  }

  void createstackframe(CallExpr *callexpr) {
    // 栈帧按照 实参引用 局部数据 排布
    // 在当前栈帧获取实参的值
    FunctionDecl *callee = callexpr->getDirectCallee()->getDefinition();
    int paramCount = callee->getNumParams();
    assert(paramCount == callexpr->getNumArgs());

    StackFrame newFrame = StackFrame();
    for (int i = 0; i < paramCount; i++) {
      //  函数参数可能是立即数【是一个stmt】
      // 也可能是 declrefexp【是一个stmt】
      // 还可能是其他 stm val
      newFrame.bindDecl(callee->getParamDecl(i),
                        this->mStack.back().getStmtVal(callexpr->getArg(i)));
    }
    // 创建栈帧并写入实参
    this->mStack.push_back(newFrame);
  }

  // 设置ReturnStmt的实值
  void returnstmt(ReturnStmt *returns) {
    // 获取返回值引用，从栈帧或者全局变量区获取实值
    // 并在栈帧中添加返回值表达式与实际值的绑定
    Expr *returnval = returns->getRetValue();
    if (returnval) {  // 返回值不为空
      int64_t val = this->mStack.back().getStmtVal(returnval);
      this->mStack.back().bindStmt(returns, val);
      this->mStack.back().setReturnval(val);
    }
  }

  void exitfun(CallExpr *callexpr) {
    // 如果有，保存callee栈帧中的返回值
    int64_t returnval = this->mStack.back().getReturnval();

    // 释放callee函数栈帧
    this->mStack.pop_back();
    // 如果有返回值，在caller函数栈帧更新callexpr的实际值
    this->mStack.back().bindStmt(callexpr, returnval);
  }

  /// 返回值表示是否为内建函数, 目前无法识别翻译单元外的函数
  bool builtinfunc(CallExpr *callexpr) {
    int64_t val = 0;
    FunctionDecl *callee = callexpr->getDirectCallee();
    if (callee == mInput) {
      llvm::errs() << "Please Input an Integer Value : ";
      scanf("%ld", &val);
      mStack.back().bindStmt(callexpr, val);
      return true;
    } else if (callee == mOutput) {
      Expr *decl = callexpr->getArg(0);
      val = mStack.back().getStmtVal(decl);
      llvm::errs() << val;
      mStack.back().bindStmt(callexpr, 0);
      return true;
    } else if (callee == mMalloc) {
      int64_t size = mStack.back().getStmtVal(callexpr->getArg(0));
      // 给malloc绑定一个指针地址
      int64_t *mallocptr = (int64_t *)malloc(size);
      mStack.back().bindStmt(callexpr, reinterpret_cast<int64_t>(mallocptr));
      // printf("malloc addr %p \n", mallocptr);
      return true;
    } else if (callee == mFree) {
      int64_t *ptr = reinterpret_cast<int64_t *>(
          mStack.back().getStmtVal(callexpr->getArg(0)));
      free(ptr);
      return true;
    } else {
      /// You could add your code here for Function call Return
      return false;
    }
  }

  /// 把 IntegerLiteral 和 CharacterLiteral 这类常量也保存到栈帧
  void literal(Expr *expr) {
    if (IntegerLiteral *literal = dyn_cast<IntegerLiteral>(expr)) {
      // clang/AST/Expr.h: class APIIntStorage
      mStack.back().bindStmt(expr, literal->getValue().getSExtValue());
    } else if (CharacterLiteral *literal = dyn_cast<CharacterLiteral>(expr)) {
      // 这块尚未验证正确性
      mStack.back().bindStmt(expr, literal->getValue());
    }
  }

  // a[i] 这样的表达式，在clang ast中是一个 lvalue
  void arraysubscribe(ArraySubscriptExpr *arraysubscriptexpr) {
    Expr *base =
        arraysubscriptexpr->getBase();  // 存放了一个ImplicitCastExpr
                                        //  解释执行栈帧中存放了数组首地址
    Expr *index = arraysubscriptexpr->getIdx();  // index 值
    // 假定数组元素都声明为 int64 类型，暂不考虑其他类型的数组
    int64_t *basePtr =
        reinterpret_cast<int64_t *>(mStack.back().getStmtVal(base));
    int64_t indexVal = mStack.back().getStmtVal(index);
    int64_t *elementPtr = basePtr + indexVal;
    mStack.back().bindStmt(arraysubscriptexpr,
                           reinterpret_cast<int64_t>(elementPtr));
  }

  void ueot(UnaryExprOrTypeTraitExpr *ueotexpr) {
    // 本次sizeof仅涉及 int以及int *
    // 在解释执行中，为了方便，int被拓展称为int64_t类型
    // 这里申请空间时也按照 int64_t 和 int* 申请空间
    UnaryExprOrTypeTrait kind = ueotexpr->getKind();
    int64_t result = 0;
    switch (kind) {
      default:
        llvm::errs() << "Unhandled UEOT.";
        break;
      case UETT_SizeOf:
        result = 8;  // int64_t 和 int64_t * 两种类型
        break;
    }
    mStack.back().bindStmt(ueotexpr, result);
  }

  void paren(ParenExpr *parenexpr) {
    Expr *parensub = parenexpr->getSubExpr();
    int64_t val = this->mStack.back().getStmtVal(parensub);
    this->mStack.back().bindStmt(parenexpr, val);
  }
  int64_t getExprVal(Expr *exp) { return mStack.back().getStmtVal(exp); }

  // 判断声明的作用域是全局还是局部栈帧，赋值
  void setDeclVal(Decl *decl, int64_t val) {
    DeclContext *parentcontext = decl->getDeclContext();
    // 判断引用的变量区域，是全局还是局部
    if (parentcontext->isTranslationUnit()) {
      golbalVars[decl] = val;
    } else if (parentcontext->isFunctionOrMethod()) {
      this->mStack.back().bindDecl(decl, val);
    } else {
      std::cout << "unsupported decl scope " << std::endl;
      assert(1);
    }
  }
};
